package cuit.pymjl;

import org.junit.jupiter.api.Test;

import java.util.*;
import java.util.concurrent.CopyOnWriteArrayList;
import java.util.concurrent.ThreadLocalRandom;
import java.util.concurrent.atomic.AtomicLong;
import java.util.concurrent.atomic.LongAdder;
import java.util.concurrent.locks.LockSupport;

/**
 * @author Pymjl
 * @version 1.0
 * @date 2022/7/4 10:45
 **/
public class Content {
    @Test
    void test() {
        // 1. 创建一个Random对象
        Random random = new Random();
        for (int i = 0; i < 10; i++) {
            // 2.输出10个[0,5)的随机数
            System.out.println(random.nextInt(5));
        }
    }

    @Test
    void testThreadLocalRandom() {
        // 1. 创建一个Random对象
        ThreadLocalRandom random = ThreadLocalRandom.current();
        for (int i = 0; i < 10; i++) {
            // 2.输出10个[0,5)的随机数
            System.out.println(random.nextInt(5));
        }
    }

    @Test
    void testAtomic() {
        AtomicLong atomicLong = new AtomicLong();
        System.out.println(atomicLong.incrementAndGet());
        System.out.println(atomicLong.decrementAndGet());
        System.out.println(atomicLong.getAndIncrement());
        System.out.println(atomicLong.getAndDecrement());
    }

    @Test
    void testCopyOnWriteList() {
        CopyOnWriteArrayList<Integer> list = new CopyOnWriteArrayList<>();
        list.add(1);
        list.get(0);
        list.add(2);
        list.set(1, 3);
        System.out.println(Arrays.toString(list.toArray()));
    }

    @Test
    void testTree() {
        Deque<Integer> deque = new ArrayDeque<>();

    }

    @Test
    void testLockSupport() throws InterruptedException {
        // 1. 创建一个子线程
        Thread thread = new Thread(() -> {
            System.out.println("child thread begin park!");
            // 2. 循环判断线程是否被中断，防止虚假唤醒
            while (!Thread.currentThread().isInterrupted()) {
                LockSupport.park();
            }
            // 3. 如果被中断，则打印提示信息
            System.out.println("child thread unpark!");
        });

        // 4. 启动子线程
        thread.start();
        // 5. 主线程睡眠1秒
        Thread.sleep(1000);
        // 6. 打印提示信息
        System.out.println("main thread begin unpark!");
        // 7. 打断子线程，让子线程立即返回
        thread.interrupt();
    }

    @Test
    void testAl() {
        System.out.println(1 << 2);
    }

    List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> paths = new LinkedList<>();

    @Test
    void testBacktrack() {
        combine(4, 2);
        System.out.println(res);
    }

    public List<List<Integer>> combine(int n, int k) {
        backTree(n, k, 1);
        return res;

    }

    private void backTree(int n, int k, int startIndex) {
        if (paths.size() == k) {
            res.add(new ArrayList<>(paths));
            return;
        }

        for (int i = startIndex; i <= n - (k - paths.size()) + 1; i++) {
            paths.add(i);
            backTree(n, k, i + 1);
            paths.removeLast();
        }
    }

    @Test
    void testBackTree() {
        System.out.println(combinationSum3(3, 7));
    }

    public List<List<Integer>> combinationSum3(int k, int n) {
        backtrack(k, n, 1, 0);
        return res;
    }

    private void backtrack(int k, int targetSum, int startIndex, int sum) {
        if (sum > targetSum) return;
        if (paths.size() == k) {
            if (sum == targetSum) {
                res.add(new ArrayList<>(paths));
            }
            return;
        }

        for (int i = startIndex; i <= 9 - (k - paths.size()) + 1; i++) {
            sum += i;
            paths.add(i);
            backtrack(k, targetSum, i + 1, sum);
            sum -= i;
            paths.removeLast();
        }
    }

    List<String> resList = new ArrayList<>();
    StringBuilder tmp = new StringBuilder();

    @Test
    void testLetterCombinations() {
        System.out.println(letterCombinations("234"));
    }

    public List<String> letterCombinations(String digits) {
        if (digits == null || digits.length() == 0) {
            return resList;
        }
        String[] letterList = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        getString(digits, letterList, 0);
        return resList;
    }

    private void getString(String digits, String[] letterList, int depth) {
        //结束条件
        if (depth == digits.length()) {
            resList.add(tmp.toString());
            return;
        }
        //处理逻辑,进行回溯
        //先获取当前数字所对应的字符串
        String letters = letterList[digits.charAt(depth) - '0'];

        for (int i = 0; i < letters.length(); i++) {
            //获取第一个字母
            tmp.append(letters.charAt(i));
            //回溯遍历
            getString(digits, letterList, depth + 1);
            //删除
            tmp.deleteCharAt(tmp.length() - 1);
        }
    }

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        Arrays.sort(candidates);
        getSum(candidates, target, path, res, 0, 0);
        return res;
    }

    private void getSum(int[] candidates, int target, List<Integer> path,
                        List<List<Integer>> res, int startIndex, int sum) {
        //结束条件
        if (sum == target) {
            res.add(new ArrayList<>(path));
            return;
        }
        //回溯
        for (int i = startIndex; i < candidates.length; i++) {
            sum += candidates[i];
            //如果此时sum已经大于target，则跳出循环（剪枝操作,注意，这里的前提是已经对数组排过序）
            if (sum > target) break;
            path.add(candidates[i]);
            //利用递归来循环
            getSum(candidates, target, path, res, i, sum);
            //移除最后的元素
            path.remove(path.size() - 1);
            sum -= candidates[i];
        }

    }

    @Test
    void getSum() {
        int[] array = {2, 3, 6, 7};
        System.out.println(combinationSum(array, 7));
    }

    public int movingCount(int m, int n, int k) {
        if(k==0) return 1;
        int cnt=1;
        //动态规划的状态数组
        boolean [][] dp=new boolean[m][n];
        dp[0][0]=true;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                //判断边界条件
                if((i==0&&j==0) || get(i)+get(j)>k){
                    continue;
                }
                //递推公式
                if(i-1>=0){
                    dp[i][j]=dp[i-1][j];
                }
                if(j-1>=0){
                    dp[i][j]=dp[i][j-1];
                }
                cnt+=dp[i][j]?1:0;
            }
        }
        return cnt;

    }

    private int get(int x) {
        int res = 0;
        while (x != 0) {
            res += x % 10;
            x /= 10;
        }
        return res;
    }

}
